/*************************************************************************
 * File Name:    NQueen_II.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: 2013/11/4 10:48:10
 * 
 * Description:  
 |------------------------------------------------------------------------
 | Problem: Follow up for N-Queens problem.
 |
 | Now, instead outputting board configurations,
 | return the total number of distinct solutions.
 |------------------------------------------------------------------------
 ************************************************************************/

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>

using namespace std;

class Solution {
private:
    void dfs(int row, int ld, int rd, int upperlim, int &ans)
    {
        if (row == upperlim) {
            ++ans;
            return;
        }
        int pos = upperlim & ~(row | ld | rd);
        while (pos != 0) {
            int p = pos & -pos;
            dfs(row | p, (ld | p ) << 1, (rd | p) >> 1, upperlim, ans);
            pos -= p;
        }
    }

public:
    int totalNQueens(int n)
    {
        int upperlim = (1 << n) - 1;
        int ans = 0;
        
        for (int i = 0; i < n / 2; ++i) {
            dfs(1 << i, 1 << (i + 1), 1 << (i - 1), upperlim, ans);
        }
        ans *= 2;
        if (n & 1) {
            n >>= 1;
            dfs(1 << n, 1 << (n + 1), 1 << (n - 1), upperlim, ans);
        }
        return ans;
    }
};

int
main(int argc, char *argv[])
{
    Solution sol;
    int n = 4;

    cout << sol.totalNQueens(n) << endl;

    return 0;
}
